cutehammond.dev

[BOJ 3654] L퍼즐

2024년 3월 19일
알고리즘2-SAT

문제 소개

문제 링크 : https://boj.kr/3654

Tier : Diamond IV

Tag : 2-SAT

3칸을 차지하는 L모양의 퍼즐 조각이 있다. 중간은 검은 색이며, 나머지 두 칸은 하얀 색이다.

각 테스트 케이스마다 N * M 크기의 패턴이 주어지는데,

우리는 해당 퍼즐 조각을 적절히 놓았을 때 패턴을 온전히 만들 수 있는지에 대한 여부를 확인해야 한다.

이때, 퍼즐 조각은 회전 가능하지만 겹칠 수 없다.

풀이

1. 일반적인 규칙 찾기

패턴 내의

2. 유효하지 않은 케이스 찾기

패턴 내의

3. 위의 규칙을 토대로 2-SAT으로 모델링하기

어떻게 하면 이 규칙을 논리식으로 변환할 수 있을까?

특정 변수 a, b, c, ...에 대해,

  1. (a v b) : a 또는 b가 true여야 성립
  2. (a v a) : a가 true여야 성립
  3. (!a v !b) ^ (!a v !c) ^ ... : a, b, c, ... 중 1개 이하만 true여야 성립
  4. (!a v b) ^ (a v !b) ^ (!a v c) ^ (a v !c) ^ ... : a, b, c, ... 모두 true이거나 false여야 성립

등의 방식으로 논리식을 모델링할 수 있다.

맹점 1

이를 이용하여 **규칙 (b)**의 일부를 충족하지만, 검은 색 칸 전부 포함되지 않는 경우도 생길 수 있다.

그러나, 이 맹점은 규칙 (c)를 통해 해결할 수 있다.

왜냐하면, 저런 상황이 올 경우 하얀 색 칸이 남게 되기 때문이다.

맹점 2

특정한 검은 색 칸에 대해, 주변의 하얀 색 칸이 가로 세로당 하나씩만 붙어야 하는 **조건 (a)**는 어떻게 충족시켜야 할까?

이러한 문제점을 다음과 같은 변수 설정으로 해결할 수 있다.

검은 색 칸에 인접한 가로 칸 중, 왼쪽에 존재하는 하얀 칸을 false, 오른쪽에 존재하는 하얀 칸을 true로 간주하여 변수를 설정한다.

세로 칸의 경우에도 마찬가지이다.

특정 변수는 무조건 true 또는 false이므로, 논리식을 이용하지 않고 변수 설정만으로 해결할 수 있다.

나머지 규칙 (d), (e)의 경우 특정 칸에 겹치는 변수를 모두 몰아넣어 (b)를 구성할 때 같이 체크하면 된다.

코드

1
#include <bits/stdc++.h>

2
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

3


4
#define BLANK 0

5
#define BLACK 1

6
#define WHITE 2

7
#define MAX 1010101

8


9
using namespace std;

10


11
vector<int> nodes[502][502], graph[MAX];

12
stack<int> candidate;

13


14
int discovered[MAX], sccIDs[MAX];

15
int puzzle[502][502];

16


17
int nodeID, sccID;

18
int N, M, whiteID;

19
bool possible = true;

20


21
// 테스트 케이스마다 초기화한다.

22
void init() {

23
    for (int i = 0; i < 502; i++) {

24
        for (int j = 0; j < 502; j++) {

25
            puzzle[i][j] = BLANK;

26
            nodes[i][j] = vector<int>();

27
        }

28
    }

29


30
    for (int i = 0; i < MAX; i++) {

31
        graph[i] = vector<int>();

32
    }

33


34
    candidate = stack<int>();

35
    possible = true;

36


37
    nodeID = sccID = 1;

38
    whiteID = 0;

39


40
    memset(discovered, 0, sizeof discovered);

41
    memset(sccIDs, 0, sizeof sccIDs);

42
}

43


44
// SCC를 형성한다.

45
int createSCC(int node) {

46
    int id = discovered[node] = nodeID++;

47
    candidate.push(node);

48


49
    for (auto next : graph[node]) {

50
        if (!discovered[next])

51
            id = min(id, createSCC(next));

52


53
        else if (!sccIDs[next])

54
            id = min(id, discovered[next]);

55
    }

56


57
    if (id == discovered[node]) {

58
        while (true) {

59
            int top = candidate.top();

60
            candidate.pop();

61


62
            sccIDs[top] = sccID;

63


64
            if (top == node)

65
                break;

66
        }

67


68
        sccID++;

69
    }

70


71
    return id;

72
}

73


74
// 패턴 매치가 가능한 지 체크한다.

75
void check() {

76
    for (int i = 0; i < whiteID; i++) {

77
        if (!discovered[i]) createSCC(i);

78
    }

79


80
    for (int i = 0; i < whiteID; i += 4) {

81
        int left = i, right = i + 1, top = i + 2, bottom = i + 3;

82


83
        if ((sccIDs[left] == sccIDs[right]) || (sccIDs[top] == sccIDs[bottom])) {

84
            possible = false;

85
            return;

86
        }

87
    }

88
}

89


90
// 패턴 정보를 토대로 2-SAT 그래프를 모델링한다.

91
void analyse() {

92
    // 1. B 기준

93
    for (int i = 1; i <= N; i++) {

94
        for (int j = 1; j <= M; j++) {

95
            if (puzzle[i][j] != BLACK) continue;

96


97
            // 1-1. Horizontal

98
            int left = whiteID, right = whiteID + 1;

99


100
            if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] == WHITE) {

101
                nodes[i][j - 1].push_back(left);

102
                nodes[i][j + 1].push_back(right);

103
            }

104


105
            else if (puzzle[i][j - 1] != WHITE && puzzle[i][j + 1] == WHITE) {

106
                nodes[i][j + 1].push_back(right);

107


108
                // 오른쪽 W가 무조건 들어가야 한다.

109
                graph[left].push_back(right);

110
            }

111


112
            else if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] != WHITE) {

113
                nodes[i][j - 1].push_back(left);

114


115
                // 왼쪽 W가 무조건 들어가야 한다.

116
                graph[right].push_back(left);

117
            }

118


119
            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.

120
            else {

121
                possible = false;

122
                return;

123
            }

124


125
            // 1-2. Vertical

126
            int top = whiteID + 2, bottom = whiteID + 3;

127


128
            if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] == WHITE) {

129
                nodes[i - 1][j].push_back(top);

130
                nodes[i + 1][j].push_back(bottom);

131
            }

132


133
            else if (puzzle[i - 1][j] != WHITE && puzzle[i + 1][j] == WHITE) {

134
                nodes[i + 1][j].push_back(bottom);

135


136
                // 아래쪽 W가 무조건 들어가야 한다.

137
                graph[top].push_back(bottom);

138
            }

139


140
            else if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] != WHITE) {

141
                nodes[i - 1][j].push_back(top);

142


143
                // 위쪽 W가 무조건 들어가야 한다.

144
                graph[bottom].push_back(top);

145
            }

146


147
            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.

148
            else {

149
                possible = false;

150
                return;

151
            }

152


153
            whiteID += 4;

154
        }

155
    }

156


157
    // 2. W 기준

158
    for (int i = 1; i <= N; i++) {

159
        for (int j = 1; j <= M; j++) {

160
            if (puzzle[i][j] != WHITE) continue;

161


162
            // W가 어떤 B에도 인접하지 않은 경우 L퍼즐을 만들 수 없다.

163
            if (nodes[i][j].empty()) {

164
                possible = false;

165
                return;

166
            }

167


168
            int U = (int) nodes[i][j].size();

169


170
            // 2-1. B가 하나인 경우, 이 W는 해당 B를 무조건 선택해야 한다.

171
            if (U == 1) {

172
                int v = nodes[i][j][0];

173
                graph[v ^ 1].push_back(v);

174


175
                continue;

176
            }

177


178
            // 2-2. 이들 중 두 개 이상을 만족시키지 않도록 한다.

179
            for (int x = 0; x < U - 1; x++) {

180
                int vx = nodes[i][j][x];

181


182
                for (int y = x + 1; y < U; y++) {

183
                    int vy = nodes[i][j][y];

184


185
                    // (!x1 v !y1) = y1 -> x2, x1 -> y2

186
                    graph[vy].push_back(vx ^ 1);

187
                    graph[vx].push_back(vy ^ 1);

188
                }

189
            }

190
        }

191
    }

192
}

193


194
int main() {

195
    FAST_IO;

196
    int T; cin >> T;

197


198
    while (T--) {

199
        init();

200


201
        // 1. 입력 받기

202
        cin >> N >> M;

203


204
        int white = 0, black = 0;

205


206
        for (int i = 1; i <= N; i++) {

207
            for (int j = 1; j <= M; j++) {

208
                char c; cin >> c;

209


210
                if (c == 'B') { black++; puzzle[i][j] = BLACK; }

211
                if (c == 'W') { white++; puzzle[i][j] = WHITE; }

212
                if (c == '.') { puzzle[i][j] = BLANK; }

213
            }

214
        }

215


216
        if (white != black << 1) {

217
            cout << "NO" << "\n";

218
            continue;

219
        }

220


221
        // 2. 패턴을 그래프화

222
        analyse();

223


224
        if (!possible) {

225
            cout << "NO" << "\n";

226
            continue;

227
        }

228


229
        // 3. 패턴 매칭 체크

230
        check();

231


232
        cout << (possible ? "YES" : "NO") << "\n";

233
    }

234


235
    return 0;

236
}

237